//#include <iostream>
//#include <fstream>
//#include <sstream>
//#include <string>
//#include <unordered_map>
//#include <queue>
//#include <set>
//#include <vector>
//#include <ctime>
//#include <algorithm>
//#include <assert.h>
//#include <math.h>
//#include <random>
#include<bits/stdc++.h>

using namespace std;

// 客户节点
struct CNode{
	string name;                    //客户节点的ID，ID字符串的长度不超过 2
	vector<int> demandSeqs;         //客户节点的需求序列（即每时刻的带宽需求），其值不超过 550,000MB
	vector<int> validEs;            //客户节点包含的有效时延范围内的边缘节点序号
	CNode(){}//空参构造器
	CNode(string name){//带参构造器
		this->name = name;
	}
};
// 边缘节点
struct ENode{
	string name;                      //边缘节点的ID，ID字符串的长度不超过 2
	int bandWidth;                    //边缘节点的带宽上限，其值不超过 1,000,000MB
	vector<int> validCs;              //边缘节点包含的有效时延范围内的客户节点序号
	ENode(){}//空参构造器
	ENode(string name, int bandWidth){//带参构造器
		this->name = name;
		this->bandWidth = bandWidth;
	}
};                                   
								      
// 定义全局变量                       
int T, M, N;                           //T表示时刻数(1<T≤8928)，M表示客户节点数(1≤𝑀≤35)，N表示边缘节点数(1≤𝑁≤135)
int LIMIT_QoS;                         //QoS约束上限
vector<string> timeSeqs;               //时间序列，长度为 T
vector<CNode> cNodes;                  //客户节点，长度为 M
vector<ENode> eNodes;                  //边缘节点，长度为 N
unordered_map<string, int> cIdxs;      //记录客户节点对应的序号
unordered_map<string, int> eIdxs;      //记录边缘节点对应的序号
vector<vector<int>> qos;               //边缘节点到客户节点的时延(0<QoS≤1000ms)，大小为 N*M
vector<vector<vector<int>>> timeAns; //ans表示每时刻，每个客户节点，获取每个边缘节点的流量。在某时刻，每一行满足客户流量需求，每一列满足边缘节点带宽上限约束

// 定义文件所在路径
# define DEMAND_CSV "/data/demand.csv"
# define SITE_BANDWIDTH_CSV "/data/site_bandwidth.csv"
# define QOS_CSV "/data/qos.csv"
# define CONFIG_INI "/data/config.ini"
# define OUTPUT_FILE "/output/solution.txt"
//# define DEMAND_CSV "./pressure_data/demand.csv"
//# define SITE_BANDWIDTH_CSV "./pressure_data/site_bandwidth.csv"
//# define QOS_CSV "./pressure_data/qos.csv"
//# define CONFIG_INI "./pressure_data/config.ini"


/********* 读数据 ***************/
string Trim(string& str){
	str.erase(0,str.find_first_not_of(" \t\r\n"));
	str.erase(str.find_last_not_of(" \t\r\n") + 1);
	return str;
}
// 读取配置文件
void readConfig(){
	ifstream fp(CONFIG_INI, ios::in);
	string line,tempstr;
	getline(fp, line);//跳过第一行
	getline(fp, line);
	size_t pos = line.find('=');
	string key = line.substr(0, pos);
	LIMIT_QoS = stoi(line.substr(pos+1));
	fp.close();
}
// 读取所有客户节点在不同时刻的带宽需求
void readDemandCsv(){
	ifstream fin(DEMAND_CSV);
	string line, field;
	// 处理第一行
	getline(fin, line);
	istringstream sin(line);//string数据流化
	getline(sin, field, ',');//跳过第一行第一个元素
	int client_number = 0;
	while(getline(sin, field, ',')){
		field = Trim(field);
		cNodes.push_back(CNode{field});
		cIdxs[field] = client_number++;
	}
	M = client_number;//客户节点数量
	//处理剩余行
	while(getline(fin, line)){
		istringstream iss(line);//string数据流化
		getline(iss, field, ',');//每行第一个元素形成时间序列
		timeSeqs.push_back(Trim(field));
		client_number = 0;
		while(getline(iss, field, ',')){
			field = Trim(field);
			CNode &node= cNodes[client_number++];
			node.demandSeqs.push_back(stoi(field));
		}
	}
	T = timeSeqs.size();//时刻数量
}
// 读取所有边缘节点的带宽上限
void readSiteBandWidthCsv(){
	ifstream fin(SITE_BANDWIDTH_CSV);
	string line, name, size;
	getline(fin, line);//跳过第一行
	//处理剩余行
	int edge_number = 0;
	while(getline(fin, line)){
		istringstream sin(line);//string数据流化
		getline(sin, name, ',');//每行第一个元素
		getline(sin, size, ',');//每行第二个元素
		size = Trim(size);
		eNodes.push_back(ENode{name, stoi(size)});
		eIdxs[name] = edge_number++;
	}
	N = eNodes.size(); //边缘节点数量
}
// 读取边缘节与客户节点之间的网络时延
void readQosCsv(){
	//初始化N*M大小的qos矩阵
	for(int n=0; n<N; n++){
		vector<int> temp(M);
		qos.push_back(temp);
	}
	ifstream fin(QOS_CSV);
	string line, clientName, edgeName, q;
	vector<string> clienNames;//记录该文件第一行中的客户节点名
	getline(fin, line);
	istringstream sin(line);
	getline(sin, q, ',');//忽略首行第一个元素
	while(getline(sin, clientName, ',')) clienNames.push_back(Trim(clientName));
	//处理其余行
	int eIdx, cIdx;
	while(getline(fin, line)){
		istringstream iss(line);//string数据流化
		getline(iss, edgeName, ',');//每行第一个元素
		int c = 0;
		eIdx = eIdxs[edgeName];
		while(getline(iss, q, ',')){
			q = Trim(q);
			cIdx = cIdxs[clienNames[c++]];
			qos[eIdx][cIdx] = stoi(q);
		}
	}
}
// 读文件
void readData(){
	readConfig();
	readDemandCsv();
	readSiteBandWidthCsv();
	readQosCsv();
	// 计算每个客户节点的 validEs
	for(int c=0; c<M; c++){
		CNode &node = cNodes[c];
		for(int e=0; e<N; e++){
			if(qos[e][c] < LIMIT_QoS){
				node.validEs.push_back(e);
			}
		}
	}
	// 计算每个边缘节点的 validCs
	for(int e=0; e<N; e++){
		ENode &node = eNodes[e];
		for(int c=0; c<M; c++){
			if(qos[e][c] < LIMIT_QoS){
				node.validCs.push_back(c);
			}
		}
	}
}
/**********************************/

/***** 写结果 *****/
void writeResults(){
	ofstream outfile;
	outfile.open(OUTPUT_FILE);
	if(!outfile){
		cout << "error for opening ouput file" << endl;
	}else{
		for(int t=0; t<T; t++){
			for(int c=0; c<M; c++){
				//输出每个客户节点的分配方案
				outfile<<cNodes[c].name<<":";
				int num = 0;
				for(int e=0; e<N; e++){
					if(timeAns[t][c][e]>0){
						num++;
						if(num==1) outfile<<"<"<<eNodes[e].name<<","<<timeAns[t][c][e]<<">";
						else outfile<<",<"<<eNodes[e].name<<","<<timeAns[t][c][e]<<">";
					}
				}
				outfile<<endl;
			}
		}
		outfile.close();
	}
}

/***** 计算成本，按照全局变量 timeAns 计算成本 *****/
int computeCost(){
	int totalCost = 0;
	int p95 = ceil(T * 0.95)-1;
	vector<vector<int>> edgeSeqs(N, vector<int>(T,0));//每个边缘节点的带宽序列
	for(int t=0; t<T; t++){
		for(int c=0; c<M; c++){
			for(int e=0; e<N; e++){
				if(timeAns[t][c][e] > 0){
					edgeSeqs[e][t] += timeAns[t][c][e];
				}
			}
		}
	}
	for(int e=0; e<N; e++){
		sort(edgeSeqs[e].begin(), edgeSeqs[e].end());
		totalCost += edgeSeqs[e][p95];
	}
	return totalCost;
}

/***** 计算成本，按照传入的带宽剩余量 rest 来计算成本 *****/
int computeCost2(const vector<vector<int>> &rest){
	int totalCost = 0;
	int p95 = ceil(T * 0.95)-1;
	vector<vector<int>> edgeSeqs(N, vector<int>(T,0));//每个边缘节点的带宽序列
	for(int t=0; t<T; t++) for(int e=0; e<N; e++) edgeSeqs[e][t] = eNodes[e].bandWidth-rest[t][e];
	for(int e=0; e<N; e++){
		sort(edgeSeqs[e].begin(), edgeSeqs[e].end());
		totalCost += edgeSeqs[e][p95];
	}
	return totalCost;
}

/***** 网络流 *****/
class NetFlow{
public:
	int source;                     //超级源点的编号，通常为 0
	int destin;                     //超级汇点的编号，通常为 n+m+1
private:
	int INF=2147483647;             //int最大值
	int m;                          //客户节点个数
	int n;                          //边缘节点个数
	struct Edge{int to, cap, flow, rev;};
	vector<vector<Edge>> G;         //用邻接表来存图的结构
	vector<int> deps;               //bfs遍历时的层次
	//连边函数，建立正向边和反向边
	void addEdge(int from, int to, int cap){
		G[from].push_back((Edge){to, cap, 0, (int)G[to].size()});       //正向边
		G[to ].push_back((Edge){from, 0, 0, (int)G[from].size()-1});   //反向边
	}
	//宽度搜索用来标记层次，随便判断有无增广路径
	bool bfs(int s){
		for(int i=0; i<deps.size(); i++) deps[i]=-1;
		deps[s] = 0;
		queue<int> q;
		q.push(s);
		while(!q.empty()){
			int v = q.front();   //获取队头元素
			q.pop();             //删除队头元素
			for(int i=0; i<G[v].size(); i++){
				const Edge &edge = G[v][i];
				if(deps[edge.to]<0 && edge.cap>edge.flow){
					deps[edge.to] = deps[v]+1;
					q.push(edge.to);
				}
			}
		}
		//返回有无增广路径
		return deps[destin] < 0 ? false : true;
	}
	//深度搜索用来寻找增广路径
	int dfs(int v, int t, int flow, vector<int> &iter){
		if(v == t) return flow;
		for(int &i=iter[v]; i<G[v].size(); i++){
			Edge &edge = G[v][i];
			if(edge.cap>edge.flow && deps[v]==(deps[edge.to]-1)){
				int temp = dfs(edge.to, t, min(flow, edge.cap-edge.flow), iter);
				if(temp > 0){
					edge.flow += temp;
					G[edge.to][edge.rev].flow -= temp;
					return temp;
				}
			}
		}
		return 0;
	}
	
public:
	//构造函数
	NetFlow(int m, int n){  
		this->m = m;
		this->n = n;
		source = 0;
		destin = n+m+1;
		G.resize(1+n+m+1);   //按顺序编号：超级源点、n个边缘节点、m个客户节点、超级汇点
		deps.resize(1+n+m+1);
	}
	
	//默认按rest和dds来初始化，只能保证找可行解
	void initial(const vector<ENode> &ens, int t, const vector<vector<int>> &rest, const vector<vector<int>> &dds){
		for(int i=0; i<G.size(); i++) G[i].clear();
		//建立超级源点和边缘节点之间的正向边和反向边
		for(int e=0; e<n; e++){
			addEdge(source, e+1, rest[t][e]);
		}
		//建立客户节点和超级汇点之间的正向边和反向边
		for(int c=0; c<m; c++){
			addEdge(n+c+1, destin, dds[t][c]);
		}
		//建立边缘节点和有效客户之间的正向边和反向边
		for(int e=0; e<n; e++){
			for(int c:ens[e].validCs){
				addEdge(e+1, n+c+1, INF);
			}
		}
	}
	
	//可以按limitBws来初始化与超级源点相关的边：限制边缘节点的带宽，实现边缘节点带宽消耗的平均
	void flushENodeLimit(const vector<ENode> &ens, int t, const vector<vector<int>> &dds, const vector<int> &limitBws){
		for(int i=0; i<G.size(); i++) G[i].clear();
		for(int e=0; e<n; e++) addEdge(source, e+1, limitBws[e]);
		for(int c=0; c<m; c++) addEdge(n+c+1, destin, dds[t][c]);
		for(int e=0; e<n; e++){
			for(int c:ens[e].validCs){
				addEdge(e+1, n+c+1, INF);
			}
		}
	}
	
	//可以按caps来初始化边缘节点与客户节点的边：限制各边容量，实现客户节点需求的平均分配
	void flushAvg(const vector<ENode> &ens, int t, const vector<vector<int>> &rest, const vector<vector<int>> &dds, const vector<vector<int>> &caps){
		for(int i=0; i<G.size(); i++) G[i].clear();
		for(int e=0; e<n; e++) addEdge(source, e+1, rest[t][e]);
		for(int c=0; c<m; c++) addEdge(n+c+1, destin, dds[t][c]);
		for(int e=0; e<n; e++){
			for(int c:ens[e].validCs){
				addEdge(e+1, n+c+1, caps[e][c]);
			}
		}
	}
	
	//dinic算法求最大流
	int dinicMaxFlow(){
		int maxFlow = 0;
		while(bfs(source)){
			vector<int> iter(m+n+2, 0);//使用当前弧优化
			while(int flow = dfs(source, destin, INF, iter)){
				maxFlow += flow;
			}
		}
		return maxFlow;
	}
	
	//返回当前时刻的每个客户节点的流量分配方案
	vector<vector<int>> getDistributionScheme(){
		vector<vector<int>> ans(m, vector<int>(n,0));
		for(int e=0; e<n; e++){
			//第一条边为算法需要的反向边，不用管。所以 i 从1开始
			for(int i=1; i<G[e+1].size(); i++){
				const Edge &edge = G[e+1][i];
				if(edge.flow != 0){
					ans[edge.to-n-1][e] = edge.flow;
				}
			}
		}
		return ans;
	}
};

/***** 白嫖5%个时刻。注意：传入的实参会被改变 *****/
void freeUse(vector<vector<int>> &rest, vector<vector<int>> &dds){
	int p95 = ceil(T * 0.95)-1;          //95分位
	vector<int> ens(N);                  //边缘节点序号
	NetFlow netFlow(M,N);                //声明一个网络流。后面使用时，根据使用目的对边进行初始化
	vector<int> bws(N, 0);               //记录超级源点到各边缘节点之间的边的容量限制。用来对网络流做初始化
	vector<vector<int>> ans;             //用来保存网络流返回的分配方案
	for(int i=0; i<N; i++) ens[i] = i;
	
	/*while(ens.size() != 0){
		sort(ens.begin(), ens.end(), [dds](int& e1, int& e2){
			int d1 = 0;
			int d2 = 0;
			for(int t=0; t<T; t++){
				for(int c:eNodes[e1].validCs) d1 += dds[t][c];
				for(int c:eNodes[e2].validCs) d2 += dds[t][c];
			}
			return d1 < d2;
		});
		int e = ens[ens.size()-1];
		ENode &eNode = eNodes[e];             //当前边缘节点
		vector<int> validCs = eNode.validCs;  //有效客户			
		vector<int> times(T), totalDs(T);
		for(int t=0; t<T; t++){
			times[t] = t;
			for(int c:validCs) totalDs[t] += dds[t][c]/cNodes[c].validEs.size()+0.01*dds[t][c];
		}
		sort(times.begin(), times.end(), [totalDs](int &t1, int &t2){return totalDs[t1] < totalDs[t2];});
		//处理大于p95的时刻
		for(int tt=T-1; tt>p95; tt--){
			int t = times[tt];
			fill(bws.begin(), bws.end(), 0);
			bws[e] = rest[t][e];
			netFlow.flushENodeLimit(eNodes, t, dds, bws);
			netFlow.dinicMaxFlow();
			ans = netFlow.getDistributionScheme();
			for(int c=0; c<M; c++){
				for(int e=0; e<N; e++){
					timeAns[t][c][e] += ans[c][e];
					dds[t][c] -= ans[c][e];
					rest[t][e] -= ans[c][e];
				}
			}
		}
		ens.pop_back();
	}*/
	
	sort(ens.begin(), ens.end(), [](int &e1, int &e2){
		return eNodes[e1].bandWidth > eNodes[e2].bandWidth;
	});
	for(int &e:ens){
		ENode &eNode = eNodes[e];             //当前边缘节点
		vector<int> validCs = eNode.validCs;  //有效客户			
		vector<int> times(T), totalDs(T);
		for(int t=0; t<T; t++){
			times[t] = t;
			for(int c:validCs) totalDs[t] += dds[t][c]/cNodes[c].validEs.size()+0.01*dds[t][c];
		}
		sort(times.begin(), times.end(), [totalDs](int &t1, int &t2){return totalDs[t1] < totalDs[t2];});
		//处理大于p95的时刻
		for(int tt=T-1; tt>p95; tt--){
			int t = times[tt];
			fill(bws.begin(), bws.end(), 0);
			bws[e] = rest[t][e];
			netFlow.flushENodeLimit(eNodes, t, dds, bws);
			netFlow.dinicMaxFlow();
			ans = netFlow.getDistributionScheme();
			for(int c=0; c<M; c++){
				for(int e=0; e<N; e++){
					timeAns[t][c][e] += ans[c][e];
					dds[t][c] -= ans[c][e];
					rest[t][e] -= ans[c][e];
				}
			}
		}
	}
}

/***** 进行第一次模拟。(不会改变真实的剩余量和需求) *****/
vector<vector<vector<int>>> firstSimulate(vector<vector<int>> rest, vector<vector<int>> dds, vector<vector<vector<int>>> tAns){
	//通过网络流的方式来平均
	vector<NetFlow> netFlows(T, NetFlow(M,N));
	for(int t=0; t<T; t++){
		vector<vector<int>> caps(N, vector<int>(M,0));//用来初始化边缘节点和客户节点之间的边
		for(int c=0; c<M; c++){
			int cap = dds[t][c]/(cNodes[c].validEs.size())+30;
			for(int e:cNodes[c].validEs){
				caps[e][c] = cap;
			}
		}
		netFlows[t].flushAvg(eNodes, t, rest, dds, caps);
		netFlows[t].dinicMaxFlow();
		vector<vector<int>> ans = netFlows[t].getDistributionScheme();
		for(int c=0; c<M; c++){
			for(int e=0; e<N; e++){
				tAns[t][c][e] += ans[c][e];
				dds[t][c] -= ans[c][e];
				rest[t][e] -= ans[c][e];
			}
		}
	}
	return tAns;
}

/***** 进行多次模拟。为每个边缘节点尽量找到一个比较小的95分位带宽使用值。(同样，不会改变真实的剩余量和需求) *****/
vector<int> getP95Limit(const vector<vector<int>> rest, const vector<vector<int>> dds, const vector<vector<vector<int>>> tAns, int simulate_num){
	int p95 = ceil(T * 0.95)-1-1;                                          //故意多减了一个
	NetFlow netFlow(M,N);                                                  //声明一个网络流。后面使用时，根据使用目的对边进行初始化
	vector<int> bws(N, 0);                                                 //记录超级源点到各边缘节点之间的边的容量限制。用来对网络流做初始化
	vector<vector<int>> ans;                                               //用来保存网络流返回的分配方案
	vector<vector<vector<int>>> timeAns_ = firstSimulate(rest, dds, tAns); //先模拟一次得到初始的95分位带宽使用值。传入的实参不会被改变
	vector<vector<int>> eSeqs(N, vector<int>(T,0));                        //每个边缘节点的带宽序列
	vector<int> eHis(N, 0);                                                //记录为每个边缘节点找到的比较小的95分位带宽使用值
	//计算第一次模拟找到的 eHis 值
	for(int t=0; t<T; t++) for(int c=0; c<M; c++) for(int e=0; e<N; e++) if(timeAns_[t][c][e] > 0) eSeqs[e][t] += timeAns_[t][c][e];
	for(int e=0; e<N; e++){sort(eSeqs[e].begin(), eSeqs[e].end()); eHis[e] = eSeqs[e][p95];}
	
	vector<vector<int>> rest_ = rest;                                      //复制一份数据，继续模拟
	vector<vector<int>> dds_ = dds;                                        //复制一份数据，继续模拟
	for(int i=0; i<simulate_num; i++){
		timeAns_ = tAns;
		rest_ = rest;
		dds_ = dds;
		for(int t=0; t<T; t++){
			//用 eHis 值来限制每个边缘节点的可分配带宽
			for(int e=0; e<N; e++) bws[e] = max(0, eHis[e] - (eNodes[e].bandWidth - rest[t][e])-20);
			netFlow.flushENodeLimit(eNodes, t, dds, bws);
			netFlow.dinicMaxFlow();
			ans = netFlow.getDistributionScheme();
			for(int c=0; c<M; c++){
				for(int e=0; e<N; e++){
					timeAns_[t][c][e] += ans[c][e];
					dds_[t][c] -= ans[c][e];
					rest_[t][e] -= ans[c][e];
				}
			}
		}
		for(int t=0; t<T; t++){
			for(int c=0; c<M; c++){
				if(dds_[t][c]==0) continue;
				vector<int> &validEs = cNodes[c].validEs;
				while(dds_[t][c] != 0){
					for(int &e:validEs){
						if(rest_[t][e] > 0){
							rest_[t][e]--;
							dds_[t][c]--;
							timeAns_[t][c][e]++;
						}
						if(dds_[t][c]==0) break;
					}
				}
			}
		}
		//重新计算该次找到的 eHis 值。理论上讲，它应该更小一些
		for(int e=0; e<N; e++) fill(eSeqs[e].begin(), eSeqs[e].end(), 0);
		for(int t=0; t<T; t++) for(int c=0; c<M; c++) for(int e=0; e<N; e++) if(timeAns_[t][c][e] > 0) eSeqs[e][t] += timeAns_[t][c][e];
		for(int e=0; e<N; e++){sort(eSeqs[e].begin(), eSeqs[e].end()); eHis[e] = eSeqs[e][p95];}
	}
	//返回找到的 eHis
	return eHis;
}

/***** 处理带宽需求 *****/
void handleDemands(){
	int p95 = ceil(T * 0.95)-1;                           //95分位
	vector<vector<int>> rest(T, vector<int>(N, 0));       //记录某时刻某边缘节点剩余带宽
	vector<vector<int>> dds(T, vector<int>(M, 0));        //记录某时刻某客户节点剩余需求
	for(int t=0; t<T; t++){
		for(int e=0; e<N; e++) rest[t][e] = eNodes[e].bandWidth;
		for(int c=0; c<M; c++) dds[t][c] = cNodes[c].demandSeqs[t];
	}
	
	// 免费使用5%个时刻
	freeUse(rest, dds);
	
	// 进行多次模拟，为每个边缘节点尽量找到一个比较小的95分位带宽使用值，然后通过这个值来优化
	NetFlow netFlow(M,N);                //声明一个网络流。后面使用时，根据使用目的对边进行初始化
	vector<int> bws(N, 0);               //记录超级源点到各边缘节点之间的边的容量限制。用来对网络流做初始化
	vector<vector<int>> ans;             //用来保存网络流返回的分配方案
	vector<int> eHis = getP95Limit(rest, dds, timeAns, 250);
	for(int t=0; t<T; t++){
		for(int e=0; e<N; e++) bws[e] = max(0, (eHis[e] - (eNodes[e].bandWidth - rest[t][e])-20));
		netFlow.flushENodeLimit(eNodes, t, dds, bws);//用来历史值eHis来限制每个边缘节点的可分配带宽
		netFlow.dinicMaxFlow();
		ans = netFlow.getDistributionScheme();
		for(int c=0; c<M; c++){
			for(int e=0; e<N; e++){
				timeAns[t][c][e] += ans[c][e];
				dds[t][c] -= ans[c][e];
				rest[t][e] -= ans[c][e];
			}
		}
	}
	
	//for(int t=0; t<T; t++){
	//	int totalDs = 0;//当前时刻客户剩余的总需求
	//	for(int c=0; c<M; c++) totalDs += dds[t][c];
	//	int bw = 1;
	//	while(totalDs != 0){
	//		for(int e=0; e<N; e++) bws[e] = min(bw, rest[t][e]);
	//		netFlow.flushENodeLimit(eNodes, t, dds, bws);
	//		totalDs -= netFlow.dinicMaxFlow();
	//		ans = netFlow.getDistributionScheme();
	//		for(int c=0; c<M; c++){
	//			for(int e=0; e<N; e++){
	//				timeAns[t][c][e] += ans[c][e];
	//				rest[t][e] -= ans[c][e];
	//				dds[t][c] -= ans[c][e];
	//			}
	//		}
	//	}
	//}

	//最终通过发牌的方式补漏
	for(int t=0; t<T; t++){
		for(int c=0; c<M; c++){
			if(dds[t][c]==0) continue;
			vector<int> &validEs = cNodes[c].validEs;
			while(dds[t][c] != 0){
				for(int &e:validEs){
					if(rest[t][e] > 0){
						rest[t][e]--;
						dds[t][c]--;
						timeAns[t][c][e]++;
					}
					if(dds[t][c]==0) break;
				}
			}
		}
	}
}

// 程序主入口
int main() {
	// 读数据
	readData();
	
	// 初始化 T*M*N 的数组，用来存答案
	for(int t=0; t<T; t++){
		vector<vector<int>> ans(M, vector<int>(N,0));
		timeAns.push_back(ans);
	}
	
	// 处理需求
	handleDemands();
	
	// 写结果
	writeResults();
	// 计算成本
	//int totalCost = computeCost();
	//cout<<"Total Cost："<<totalCost<<endl;
	//
    //std::cout << "Hello world!"<<std::endl;
	return 0;
}
